from BinaryTree import *

class Solution:
    # @param {TreeNode} root
    # @param {integer} sum
    # @return {integer[][]}
    def pathSum(self, root, sum):
    	ans = []
    	self.__dfs(root, 0, sum, [], ans)
    	return ans

    def __dfs(self, node, curr, sum, track, ans):
    	#if node:
    	#	print track, node.val
    	if node is None:
    		return
    	elif curr + node.val == sum and not node.left and not node.right:
    		track.append(node.val)
    		ans.append(track[:])
    		track.pop()
    	else:
    		track.append(node.val)
    		if node.left:
    			self.__dfs(node.left, curr+node.val, sum, track, ans)
    		if node.right:
    			self.__dfs(node.right, curr+node.val, sum, track, ans)
    		track.pop()

if __name__ == '__main__':
	t = BinaryTree([1,-2,-3,1,3,-2,'#',-1])
	t.display()
	print Solution().pathSum(t.tree(), -1)